package day_6_30;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main3 {
    /**
     * 90. 子集 II
     * https://leetcode.cn/problems/subsets-ii/description/
     */
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int n;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        n = nums.length;
        dfs(0,nums);

        return ret;
    }

    public void dfs(int pos,int[] nums) {
        if(pos == n) {
            ret.add(new ArrayList<>(path));
            return;
        }

        // 选当前的数据
        int x = nums[pos];
        path.add(x);
        dfs(pos + 1,nums);
        // 回溯
        path.remove(path.size() - 1);

        // 不选x，那么当前位置及其之后的x都不能进行选择
        while(pos < n && nums[pos] == x) {
            pos++;
        }
        dfs(pos,nums);
    }
}
